P3398 仓鼠找sugar

模板题，询问树上两链是否有交

算法：

给出性质：若两树链有交，则必有其中一条链的端点的lca在另一条链上，记为P

由这个性质题目一下变水了。。。

那如何判断一个点是否在一条链上呢？

设a-b链lca为c，x-y链lca为z，且$d_c>d_z$

WAY1. dis(x,a)+dis(x,b)=dis(a,b)

显然的，不等就成三角形了

    read(x),read(y),read(u),read(v);
    int z=lca(x,y),w=lca(u,v);
    if(d[z]>d[w]){
        swap(x,u);
        swap(y,v);
        swap(z,w);
    }
    if(dis(w,x)+dis(w,y)==dis(x,y)) puts("Y");
    else puts("N");

WAY2. x是x-a的lca或x是x-b的lca

反证易得

    read(x),read(y),read(u),read(v);
    int z=lca(x,y),w=lca(u,v);
    if(d[z]>d[w]){
        swap(x,u);
        swap(y,v);
        swap(z,w);
    }
    if(lca(w,x)==w||lca(w,y)==w) puts("Y");
    else puts("N");

证明：

当然手画树猜结论是大多数人的选择

我们容易发现，如果相交，记 $x=lca(a,b)$,$y=lca(c,d)$，则必有x在c-d路径上或y在a-b路径上

首先易知两点的lca在其路径上。如果路径相交，那么x要么在相交的路径上，要么不在。我们不妨记相交的那段为e-f

如果不在，由对称性，不妨设x靠近a，那么有a到x深度递减，b到e、e到f、f到x深度递减；同样，肯定有c到f、d到e深度递减，由此可知，y必定为f，由此得证

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=1e5+5,M=N<<1;
int n,m,en,h[N],s[N],sz[N],f[N],top[N],d[N];
struct edge{int n,v;}e[M];
inline void add(const int &x,const int &y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}
void dfs1(int x){
    sz[x]=1;
    d[x]=d[f[x]]+1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==f[x]) continue;
        f[y]=x;
        dfs1(y);
        sz[x]+=sz[y];
        if(sz[s[x]]<sz[y]) s[x]=y;
    }
}
void dfs2(int x,int TOP){
    top[x]=TOP;
    if(s[x]) dfs2(s[x],TOP);
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==f[x]||y==s[x]) continue;
        dfs2(y,y);
    }
}
inline int lca(int x,int y){
    while(top[x]^top[y])
        if(d[top[x]]>d[top[y]]) x=f[top[x]];
        else y=f[top[y]];
    return d[x]<d[y]?x:y;
}
void doit(){
    int x,y,u,v;
    read(x),read(y),read(u),read(v);
    int z=lca(x,y),w=lca(u,v);
    if(d[z]>d[w]){
        swap(x,u);
        swap(y,v);
        swap(z,w);
    }
    if(lca(w,x)==w||lca(w,y)==w) puts("Y");
    else puts("N");
}
signed main(){
    read(n);read(m);
    for(int i=1,x,y;i<n;i++){
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    dfs1(1);
    dfs2(1,1);
    while(m--) doit();
}
赏

FIGHTER